Erdős–Szekeres theorem

In mathematics, the Erdős–Szekeres theorem is a finitary result that makes precise one of the corollaries of Ramsey's theorem. While Ramsey's theorem makes it easy to prove that every sequence of distinct real numbers contains either a monotonically increasing infinite subsequence, or a monotonically decreasing infinite subsequence, the result proved by Paul Erdős and George Szekeres goes further. For given r, s they showed that any sequence of length at least (r − 1)(s − 1) + 1 contains either a monotonically increasing subsequence of length r, or a monotonically decreasing subsequence of length s. The proof appeared in the same 1935 paper that mentions the Happy Ending problem.^[1]

1 Example
2 Geometric interpretation
3 Proofs
- 3.1 Pigeonhole principle
- 3.2 Dilworth's theorem
4 See also
5 References
6 External links

Example

For r = 3 and s = 2, the formula tells us that any permutation of three numbers has an increasing subsequence of length three or a decreasing subsequence of length two. Among the six permutations of the numbers 1,2,3:

1,2,3 has an increasing subsequence consisting of all three numbers
1,3,2 has a decreasing subsequence 3,2
2,1,3 has a decreasing subsequence 2,1
2,3,1 has two decreasing subsequences, 2,1 and 3,1
3,1,2 has two decreasing subsequences, 3,1 and 3,2
3,2,1 has three decreasing length-2 subsequences, 3,2, 3,1, and 2,1.

Geometric interpretation

One can interpret the positions of the numbers in a sequence as x-coordinates of points in the Euclidean plane, and the numbers themselves as y-coordinates; conversely, for any point set in the plane, the y-coordinates of the points, ordered by their x-coordinates, forms a sequence of numbers (unless two of the points have equal x-coordinates). With this translation between sequences and point sets, the Erdős–Szekeres theorem can be interpreted as stating that in any set of at least rs − r − s + 2 points we can find a polygonal path of either r − 1 positive-slope edges or s − 1 negative-slope edges. For instance, taking r = s = 5, any set of at least 17 points has a four-edge path in which all slopes have the same sign.

An example of rs − r − s + 1 points without such a path, showing that this bound is tight, can be formed by applying a small rotation to an (r − 1) by (s − 1) grid.

Proofs

The Erdős–Szekeres theorem can be proved in several different ways; Steele (1995) surveys six different proofs of the Erdős–Szekeres theorem, including the following two.^[2] Other proofs surveyed by Steele include the original proof by Erdős and Szekeres as well as those of Blackwell (1971),^[3] Hammersley (1972),^[4] and Lovász (1979).^[5]

Pigeonhole principle

Given a sequence of length (r − 1)(s − 1) + 1, label each number n_i in the sequence with the pair (a_i,b_i), where a_i is the length of the longest monotonically increasing subsequence ending with n_i and b_i is the length of the longest monotonically decreasing subsequence ending with n_i. Each two numbers in the sequence are labeled with a different pair: if i < j and n_i < n_j then a_i < a_j, and on the other hand if n_i > n_j then b_i < b_j. But there are only (r − 1)(s − 1) possible labels in which a_i is at most r − 1 and b_i is at most s − 1, so by the pigeonhole principle there must exist a value of i for which a_i or b_i is outside this range. If a_i is out of range then n_i is part of an increasing sequence of length at least r, and if b_i is out of range then n_i is part of a decreasing sequence of length at least s.

Steele (1995) credits this proof to the one-page paper of Seidenberg (1959) and calls it "the slickest and most systematic" of the proofs he surveys.^[2]^[6]

Dilworth's theorem

Another of the proofs uses Dilworth's theorem on chain decompositions in partial orders, or its simpler dual (Mirsky's theorem).

To prove the theorem, define a partial ordering on the members of the sequence, in which x is less than or equal to y in the partial order if x ≤ y as numbers and x is not later than y in the sequence. A chain in this partial order is a monotonically increasing subsequence, and an antichain is a monotonically decreasing subsequence. By Mirsky's theorem, either there is a chain of length r, or the sequence can be partitioned into at most r − 1 antichains; but in that case the largest of the antichains must form a decreasing subsequence with length at least

$\left\lceil\frac{rs-r-s%2B2}{r-1}\right\rceil=s.$

Alternatively, by Dilworth's theorem itself, either there is an antichain of length s, or the sequence can be partitioned into at most s − 1 chains, the longest of which must have length at least r.

References

^ Erdős, Paul; Szekeres, George (1935), "A combinatorial problem in geometry", Compositio Mathematica 2: 463–470, http://www.numdam.org/item?id=CM_1935__2__463_0.
^ ^a ^b Steele, J. Michael (1995), "Variations on the monotone subsequence theme of Erdős and Szekeres", in Aldous, David; Diaconis, Persi; Spencer, Joel et al., Discrete Probability and Algorithms, IMA Volumes in Mathematics and its Applications, 72, Springer-Verlag, pp. 111–131, http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf .
^ Blackwell, Paul (1971), "An alternative proof of a theorem of Erdős and Szekeres", American Mathematical Monthly 78 (3): 273–273, doi:10.2307/2317525, JSTOR 2317525 .
^ Hammersley, J. M. (1972), "A few seedlings of research", Proc. 6th Berkeley Symp. Math. Stat. Prob., University of California Press, pp. 345–394 . As cited by Steele (1995).
^ Lovász, László (1979), "Solution to Exercise 14.25", Combinatorial Problems and Exercises, North-Holland . As cited by Steele (1995).
^ Seidenberg, A. (1959), "A simple proof of a theorem of Erdős and Szekeres", Journal of the London Mathematical Society 34: 352, http://jlms.oxfordjournals.org/cgi/reprint/s1-34/3/352.pdf .

External links

Weisstein, Eric W., "Erdős-Szekeres Theorem" from MathWorld.